package leetcode_core.leetcode_1;

import org.junit.Test;

public class SuperEggDropByDpTable2 {

    public int superEggDrop(int k, int n) {
        //m最多不会超过n次(线性扫描情况)
        int[][] dp = new int[k+1][n+1];
        //base-case
        //dp[0][...]=0
        //dp[...][0]=0
        int m = 0;
        while(dp[k][m]<n){
            m++;
            for(int j = 1;j<=k;j++){
                dp[j][m] = dp[j][m-1]+dp[j-1][m-1]+1;
            }
        }
        return m;
    }
    @Test
    public void test(){
        System.out.println(superEggDrop(1,2));
        System.out.println(superEggDrop(2,6));
        System.out.println(superEggDrop(3,14));
    }
}
